/*
2385. 感染二叉树需要的总时间
https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/description/
中等 2024/11/15
*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    int amountOfTime(TreeNode* root, int start) {
    unordered_map<int,vector<int>>mp;

   function<void(TreeNode *)> dfs = [&](TreeNode *root)
    {
//function：这是一个通用的多态函数包装器，可以存储、复制和调用任何可调用目标
//Lambda 函数：这是一种匿名函数，可以在定义时立即创建并使用。Lambda 表达式的语法形式为 [capture](parameters) -> return_type { body }。
 //接受一个 TreeNode* 参数且返回 void 的函数。
        for(auto node : vector<TreeNode* >{root->left,root->right})
        {
            if(node!=nullptr)
            {
                mp[root->val].push_back(node->val);
                mp[node->val].push_back(root->val);
                dfs(node);
            }
        }
    };
        dfs(root); //建好无向图
        int ans=0;
        queue<vector<int>>qe;
        qe.push({start,0});
        unordered_set<int>visit;
        visit.insert(start);
        while(!qe.empty())
        {
            vector<int>arr=qe.front();
            qe.pop();
            int val=arr[0];
            ans=arr[1];
            for(int i : mp[val])
            {
                if(!visit.count(i))
                {
                    qe.push({i,ans+1});
                    visit.insert(i);                    
                }
            }
        }
    return ans;   
    }
};